Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much 
attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one.
 Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can 
rob tonight without alerting the police.

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

 

这道题是之前那道House Robber 打家劫舍的拓展，现在房子排成了一个圆圈，则如果抢了第一家，就不能抢最后一家，因为首尾相连了，
所以第一家和最后一家只能抢其中的一家，或者都不抢，那我们这里变通一下，如果我们把第一家和最后一家分别去掉，各算一遍能抢的最大值，
然后比较两个值取其中较大的一个即为所求。那我们只需参考之前的House Robber 打家劫舍中的解题方法，然后调用两边取较大值，代码如下：
class Solution {
public:
    int rob(vector<int> &num) {
        if (num.size() == 0) return 0;
        if (num.size() == 1) return num[0];
        vector<int> dp(num.size());
        //抢第一家到倒数第二家的最大值
        dp[0] = num[0];
        for (int i = 1; i < num.size() - 1; ++i)
            dp[i] = max(dp[i-1], (i == 1 ? 0 : dp[i-2]) + num[i]);
        int res = dp[num.size()-2];
        //抢第二家到最后一家的最大值
        dp[1] = num[1];
        for (int i = 2; i < num.size() ; ++i)
            dp[i] = max(dp[i-1], (i == 2 ? 0 : dp[i-2]) + num[i]);
        //返回两者较大的一个    
        return max(res, dp[num.size()-1]);
    }
};